package LeetCode.leetcode19;

import java.util.Stack;

public class Main {
    public static void main(String[] args) {

    }

    /**
     * 用栈stack，官方题解使用双指针
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n < 0)
            return null;
        Stack<ListNode> stack1 = new Stack<>();
        ListNode p = head;
        while (p != null) {
            stack1.push(p);
            p = p.next;
        }
        for (int i = 0; i < n - 1; i++) {
            if (stack1.empty())
                return null;
            stack1.pop();
        }
        //当前栈顶元素就是要删除的元素
        ListNode deleteNode = stack1.pop();
        //如果删除的元素就是第一个元素(head)
        if (stack1.empty()) {
            head = deleteNode.next;
        } else {
            ListNode preNode = stack1.peek();
            preNode.next = preNode.next.next;
        }
        return head;
    }

    /**
     * 双指针解法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if (n<0)
            return null;
        //构建虚拟头结点
        ListNode virtualNode = new ListNode();
        virtualNode.next = head;

        ListNode slow = virtualNode;
        ListNode high = virtualNode;
        //先让high后移n个单位
        for (int i = 0; i < n; i++) {
            if (high.next!=null){
                high = high.next;
            }
        }
        //双指针后移
        while(high.next!=null){
            slow = slow.next;
            high = high.next;
        }
        slow.next = slow.next.next;
        return virtualNode.next;
    }
}
